home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 60 / IOPROG_60.ISO / soft / c++ / gsl-1.1.1-setup.exe / {app} / src / combination / combination.c next >
Encoding:
C/C++ Source or Header  |  2001-12-12  |  3.5 KB  |  165 lines
  1. /* combination/combination.c
  2.  * based on permutation/permutation.c by Brian Gough
  3.  * 
  4.  * Copyright (C) 2001 Szymon Jaroszewicz
  5.  * 
  6.  * This program is free software; you can redistribute it and/or modify
  7.  * it under the terms of the GNU General Public License as published by
  8.  * the Free Software Foundation; either version 2 of the License, or (at
  9.  * your option) any later version.
  10.  * 
  11.  * This program is distributed in the hope that it will be useful, but
  12.  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14.  * General Public License for more details.
  15.  * 
  16.  * You should have received a copy of the GNU General Public License
  17.  * along with this program; if not, write to the Free Software
  18.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19.  */
  20.  
  21. #include <config.h>
  22. #include <gsl/gsl_errno.h>
  23. #include <gsl/gsl_combination.h>
  24.  
  25. extern int gsl_check_range ; /* defined in vector/vector.c */
  26.  
  27. size_t
  28. gsl_combination_n (const gsl_combination * c)
  29. {
  30.   return c->n ;
  31. }
  32.  
  33. size_t
  34. gsl_combination_k (const gsl_combination * c)
  35. {
  36.   return c->k ;
  37. }
  38.  
  39. size_t *
  40. gsl_combination_data (const gsl_combination * c)
  41. {
  42.   return c->data ;
  43. }
  44.  
  45. #ifndef HIDE_INLINE_STATIC
  46. size_t
  47. gsl_combination_get (const gsl_combination * c, const size_t i)
  48. {
  49.   if (gsl_check_range)
  50.     {
  51.       if (i >= c->k)        /* size_t is unsigned, can't be negative */
  52.     {
  53.       GSL_ERROR_VAL ("index out of range", GSL_EINVAL, 0);
  54.     }
  55.     }
  56.  
  57.   return c->data[i];
  58. }
  59. #endif
  60.  
  61.  
  62. int
  63. gsl_combination_valid (gsl_combination * c)
  64. {
  65.   const size_t n = c->n ;
  66.   const size_t k = c->k ;
  67.  
  68.   size_t i, j ;
  69.  
  70.   if( k > n )
  71.     {
  72.       GSL_ERROR("combination has k greater than n", GSL_FAILURE) ;
  73.     }
  74.   for (i = 0; i < k; i++) 
  75.     {
  76.       if (c->data[i] >= n)
  77.         {
  78.           GSL_ERROR("combination index outside range", GSL_FAILURE) ;
  79.         }
  80.  
  81.       for (j = 0; j < i; j++)
  82.         {
  83.           if (c->data[i] == c->data[j])
  84.             {
  85.               GSL_ERROR("duplicate combination index", GSL_FAILURE) ;
  86.             }
  87.           if (c->data[i] > c->data[j])
  88.             {
  89.               GSL_ERROR("combination index no in increasing order",
  90.             GSL_FAILURE) ;
  91.             }
  92.         }
  93.     }
  94.   
  95.   return GSL_SUCCESS;
  96. }
  97.  
  98.  
  99. int
  100. gsl_combination_next (gsl_combination * c)
  101. {
  102.   /* Replaces c with the next combination (in the standard lexicographical
  103.    * ordering).  Returns GSL_FAILURE if there is no next combination.
  104.    */
  105.   const size_t n = c->n;
  106.   const size_t k = c->k;
  107.   size_t *data = c->data;
  108.   size_t i;
  109.  
  110.   if(k == 0)
  111.     {
  112.       return GSL_FAILURE;
  113.     }
  114.   i = k - 1;
  115.  
  116.   while(i > 0 && data[i] == n - k + i)
  117.     {
  118.       i--;
  119.     }
  120.   if(i == 0 && data[i] == n - k)
  121.     {
  122.       return GSL_FAILURE;
  123.     }
  124.   data[i]++;
  125.   for(; i < k - 1; i++)
  126.     {
  127.       data[i + 1] = data[i] + 1;
  128.     }
  129.   return GSL_SUCCESS;
  130. }
  131.  
  132. int
  133. gsl_combination_prev (gsl_combination * c)
  134. {
  135.   /* Replaces c with the previous combination (in the standard
  136.    * lexicographical ordering).  Returns GSL_FAILURE if there is no
  137.    * previous combination.
  138.    */
  139.   const size_t n = c->n;
  140.   const size_t k = c->k;
  141.   size_t *data = c->data;
  142.   size_t i;
  143.  
  144.   if(k == 0)
  145.     {
  146.       return GSL_FAILURE;
  147.     }
  148.   i = k - 1;
  149.  
  150.   while(i > 0 && data[i] == data[i-1] + 1)
  151.     {
  152.       i--;
  153.     }
  154.   if(i == 0 && data[i] == 0)
  155.     {
  156.       return GSL_FAILURE;
  157.     }
  158.   data[i++]--;
  159.   for(; i < k; i++)
  160.     {
  161.       data[i] = n - k + i;
  162.     }
  163.   return GSL_SUCCESS;
  164. }
  165.